package com.linchong.dynamicprogramming.medium;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-26 14:24
 * @Description: Backpack$背包问题-lintCode92
 *
 * 给定n个物品，重量分别是正整数A0,A1,A2,...,An-1,价值分别是V0,V1,...,Vn-1
 * 一个背包最大承重是正整数M
 * 最多能带走多大价值的物品
 *
 * eg:
 *  输入：4个物品，重量为2,3,5,7,价值是1,5,2,4,,最大承重是11
 *  输出：9,(物品一+物品三，重量10，价值9)
 *
 *
 * !!! 背包问题，重量一定放在数据下标中
 *
 * 【解析】
 *  背包最大承重是M,每个装物品的方案的总重量都是0到M
 *  如果对于每个总重量，我们能知道对应的最大价值是多少，就可以知道答案
 *
 *  step1:确定状态
 *
 *  同一类似，需要直到N个物品
 *  -能否拼出重量W(w=0,1,...,M)
 *  -对于每个重量W，最大总价值是多少
 *
 *  背包问题最后一步就只有两种情况：最后一个物品是否进入背包；最后进入背包的物品是哪一个
 *
 *  最后一步：最后一个物品（重量A(n-1),价值V(n-1)）是否进入背包
 *  所有有两种情况：
 *      选择一：如果前N-1个物品能拼出W,最大总价值V，则前N个物品也能拼出W且最大总价值是V
 *
 *      选择二：如果前N-1个物品能拼出W-A(n-1),最大总价值是V，则再加上最后一个物品（重量A(n-1),价值V(n-1)),
 *      能拼出W，总价值是V+V(n-1)
 *
 *      eg: 3个物品，重量为2,3,5，价值为20,30,50，最大重量5
 *      1.前两个物品可以拼出重量5（2+3），最大价值是30，前三个物品也可以拼出重量5，价值30
 *      2.前两个可以拼出重量0，价值0，加上最后一个物品，可以拼出最大价值50,50>30,所以所有物品拼出重量5时，
 *      最大总价值为50
 *
 *  子问题：
 *      要求前N个物品能不能拼出重量0,1,...,M,以及拼出重量W能获得的最大价值
 *      需要直到前N-1个物品能不能拼出重量0,1,2,...,M,以及拼出重量W能获得多大的价值
 *
 *      状态：f[i][w] = 用前i个物品拼出重量w时最大总价值（-1表示不能拼出w）
 *
 *  step2状态转移方程
 *      设 f[i][w] = 用前i个物品拼出重量w时最大总价值（-1表示不能拼出w）
 *      f[i][w] = max{f[i-1][w],f[i-1][w-A(i-1)]+V(i-1)|w>=A(i-1)且f[i-1][w-A(i-1)]!=-1}
 *
 *    用前i个物品拼出重量w时最大总价值      用前i-1个物品拼出重量w时最大总价值  用前i-1个物品拼出重量w-A(i-1)时的总价值，加上第i个物品
 *
 *  step3初始条件和边界情况
 *      设f[i][w]=用前i个物品拼出重量w时的最大总价值（-1表示不能拼出w）
 *      f[i][w] = max{f[i-1][w],f[i-1][w-A(i-1)]+V(i-1)|w>=A(i-1)且f[i-1][w-A(i-1)]!=-1}
 *      初始条件：
 *          f[0][0] = 0,0个物品可以拼出重量0，最大总价值是0
 *          f[0][1...M] = -1,0个物品不能拼出大于0的重量
 *      边界情况：
 *          f[i-1][w-A(i-1)],只能在w>=A(i-1),并且f[i-1][w-A(i-1)]!=-1时使用
 *
 *   step4计算顺序：
 *      初始化f[0][0],f[0][1],...,f[0][M]
 *      计算前1个物品拼出各种重量的最大值，f[1][0],f[1][1],...,f[1][M]
 *      ...
 *      计算前n个物品拼出各种重量的最大值，f[1][0],f[N][1],...,f[n][M]
 *
 *      结果：Max(0<=j<=M){f[N][j]|f[N][j]!=-1}
 *
 *      时间复杂度（计算步数）：O(MN),空间复杂度（数组大小）：优化后可达到O(M)
 *
 *
 *
 *      重量放在状态里，价值放在数组里

 */
public class BackpackII {


	/**
	 *
	 * @param item 物品
	 * @param m 最大承重
	 * @param v 价值
	 * @return
	 */
	int backPack(int[] item,int m,int[] v){
		int n = item.length;
		if(n==0){
			return 0;
		}


		int[] f = new int[m+1];

		for (int i = 1; i <= m; i++) {
			f[i] = -1;
		}

		// 滚动数组，倒着算
		for (int i = 1; i <= n; i++) {
			for (int w = m; w >= 0 ; w--) {
				// updated f[w]: slides f[i][j]
				// original f[w]: slides f[i-1][w]
				//f[i][w] = max{f[i-1][w],f[i-1][w-A(i-1)]+V(i-1)|w>=A(i-1)且f[i-1][w-A(i-1)]!=-1}
				if(w>=item[i-1] && f[w-item[i-1]] != -1){
					f[w] = Math.max(f[w],f[w-item[i-1]]+v[i]);
				}

			}
		}

		int res = 0;
		for (int i = 0; i <= m ; i++) {
			if(f[i]!=-1){
				res = Math.max(res,f[i]);
			}
		}

		return res;
	}

	public static void main(String[] args) {
		int[] item = {2,3,5,7};
		int[] value = {1,2,4,7};
		int m = 10;
		BackpackII instance = new BackpackII();
		System.out.println(instance.backPack(item,m,value));
	}

}
